package leetcode.code0794;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/***
 * 托管并查集: 小常数
 *
 * 执行用时：26 ms, 在所有 Java 提交中击败了10.91%的用户
 *
 * 内存消耗：43.3 MB, 在所有 Java 提交中击败了5.45%的用户
 *
 * 通过测试用例：32 / 32
 ***/
public class Solution5 implements IDebug {

	int[][] isInfected;
	int m, n;
	int[] d = new int[] { 0, 1, 0, -1, -1, 0, 1, 0 };

	class Union {
		// 传统并查集
		int[] represent;
		int[] sizes;

		int[] stack;
		int pstack;

		// 感染源头
//		Set<Integer> infectSource;
		boolean[] infectSource;

		// 影响0，间接影响0的数量
		Map<Integer, Set<Integer>> refers;
		// 当前防火墙数量
		int[] walls;

		// 测试用
		int groupSize;
		int len;

		int[][] queue;

		public Union() {
			len = m * n;
			this.represent = new int[len];
			this.sizes = new int[len];
			this.stack = new int[len];
			this.pstack = 0;
//			this.infectSource = new HashSet<>();
			this.infectSource = new boolean[len];
			//
			queue = new int[len][3];
			this.refers = new HashMap<>();
			this.walls = new int[len];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					int index = this.index(i, j);
					this.represent[index] = index;
					this.sizes[index] = 1;
					refers.put(index, new HashSet<>());
//					this.infectSource.add(index);
					this.infectSource[index] = true;
				}
			}
			this.groupSize = len;
			this.initUnion();
		}

		private int index(int x, int y) {
			return x * n + y;
		}

		private void initUnion() {
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					int cur = isInfected[i][j];
					this.updateWalls(i, j, null, 0);
					if (cur == 1) {
						if (i > 0 && isInfected[i - 1][j] == 1) {
//							this.join(i - 1, j, i, j);
							this.join(this.index(i - 1, j), this.index(i, j));
						}
						if (j > 0 && isInfected[i][j - 1] == 1) {
//							this.join(i, j - 1, i, j);
							this.join(this.index(i, j - 1), this.index(i, j));
						}
					}
				}
			}
		}

		private void updateWalls(int x, int y, Map<Integer, Set<Integer>> join, int join2) {
			int cur = isInfected[x][y];
			int index = this.index(x, y);
			for (int i = 0; i < 8; i += 2) {
				int nextx = x + d[i], nexty = y + d[i + 1];
				int nextIndex = this.index(nextx, nexty);
				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
					if (cur == 1) {
						if (isInfected[nextx][nexty] == 0) {
							// 当前是1 ，邻接是0 ，当前防火墙数量 + 1
							this.walls[index]++;
							if (!refers.get(index).contains(nextIndex)) {
								Set<Integer> refer = refers.get(index);
								refer.add(nextIndex);
								refers.put(index, refer);
							}
						} else if (join != null) {
							int pn = this.represent(nextIndex);
							if (pn != index && this.infectSource[pn]) {
								if (join.containsKey(index)) {
									Set<Integer> set = join.get(index);
									set.add(pn);
									join.put(index, set);
								} else {
									Set<Integer> set = new HashSet<>();
									set.add(pn);
									join.put(index, set);
								}
							}
						}
					}
				}
			}
		}

		private void join(int index1, int index2) {
			int r1 = this.represent(index1);
			int r2 = this.represent(index2);
			if (r1 != r2) {
				int size1 = this.sizes[r1];
				int size2 = this.sizes[r2];
				if (size1 < size2) {
					this.represent[r1] = r2;
					this.sizes[r2] = size1 + size2;
//					this.infectSource.remove(r1);
//					this.infectSource.add(r2);
					this.infectSource[r1] = false;
					this.infectSource[r2] = true;
					this.walls[r2] = this.walls[r2] + this.walls[r1];
					this.walls[r1] = 0;
					if (refers.get(r1).size() != 0) {
						Set<Integer> refer1 = refers.get(r1);
						Set<Integer> refer2 = refers.get(r2);
						refer2.addAll(refer1);
						refers.put(r2, refer2);
						refers.put(r1, new HashSet<>());
					}
				} else {
					this.represent[r2] = r1;
					this.sizes[r1] = size1 + size2;
					this.infectSource[r1] = true;
					this.infectSource[r2] = false;
					this.walls[r1] = this.walls[r2] + this.walls[r1];
					this.walls[r2] = 0;
					if (refers.get(r2).size() != 0) {
						Set<Integer> refer1 = refers.get(r1);
						Set<Integer> refer2 = refers.get(r2);
						refer1.addAll(refer2);
						refers.put(r1, refer1);
						refers.put(r2, new HashSet<>());
					}
				}
				this.groupSize--;
			}
		}

		private int represent(int index) {
			this.pstack = 0;
			int ans = 0;
			while ((ans = this.represent[index]) != index) {
				this.stack[this.pstack++] = index;
				index = ans;
			}
			while (this.pstack > 0) {
				this.represent[this.stack[--this.pstack]] = ans;
			}
			return ans;
		}

		public void infect() {
			int pqueue = 0;
			Map<Integer, Set<Integer>> join = new HashMap<>();
			for (int index = 0; index < len; index++) {
				if (this.infectSource[index]) {
					Set<Integer> refer = refers.get(index);
					refers.put(index, new HashSet<>());
					for (Integer range : refer) {
						int i = range / n, j = range % n;
						if (isInfected[i][j] == 0) {
							isInfected[i][j] = 1;
							queue[pqueue][0] = i;
							queue[pqueue][1] = j;
							queue[pqueue++][2] = index;
							this.represent[range] = range;
						}
					}
				}
			}
			this.walls = new int[len];
			while (pqueue > 0) {
				int[] cur = queue[--pqueue];
				int x = cur[0], y = cur[1], join2 = cur[2];
				this.updateWalls(x, y, join, join2);
			}
			for (Map.Entry<Integer, Set<Integer>> entry : join.entrySet()) {
				int cur = entry.getKey();
				for (Integer join2 : entry.getValue()) {
					this.join(cur, join2);
				}
			}
		}

		public int maxWall() {
			int refer = 0, maxIndex = -1;
			for (int i = 0; i < len; i++) {
				if (this.infectSource[i]) {
					int cur = refers.get(i).size();
					if (cur > refer) {
						refer = cur;
						maxIndex = i;
					}
				}
			}
			if (maxIndex == -1) {
				return 0;
			}
			union.infectSource[maxIndex] = false;
			return this.walls[maxIndex];
		}
	}

	Union union;

	public int containVirus(int[][] isInfected) {
		this.isInfected = isInfected;
		this.m = isInfected.length;
		this.n = isInfected[0].length;
		int ans = 0;
		int wall = 0;
		union = new Union();
		do {
			if (wall != 0) {
				union.infect();
			}
			wall = union.maxWall();
			ans += wall;
		} while (wall != 0);
		return ans;
	}

//	H.printObject(isInfected);
//	H.printObject(union.walls);

	@Override
	public void debug1() {
		HelpDebug.compare(10, this.containVirus(
				HelpDebug.str2array1("[[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(4, this.containVirus(HelpDebug.str2array1("[[1,1,1],[1,0,1],[1,1,1]]")));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(13, this.containVirus(HelpDebug.str2array1("[[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]")));

	}

	@Override
	public void debug4() {
		HelpDebug.compare(38, this.containVirus(HelpDebug.str2array1(
				"[[0,1,0,1,1,1,1,1,1,0],[0,0,0,1,0,0,0,0,0,0],[0,0,1,1,1,0,0,0,1,0],[0,0,0,1,1,0,0,1,1,0],[0,1,0,0,1,0,1,1,0,1],[0,0,0,1,0,1,0,1,1,1],[0,1,0,0,1,0,0,1,1,0],[0,1,0,1,0,0,0,1,1,0],[0,1,1,0,0,1,1,0,0,1],[1,0,1,1,0,1,0,1,0,1]]")));
	}

	public static void main(String[] args) {
		Solution5 so = new Solution5();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
